/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */
int Find_Num(struct Node* head, struct Node* target)
{
    struct Node* cur = head;
    int Num = 0;
    while (cur != target)
    {
        Num++;
        cur = cur->next;
    }
    return Num;
}
struct Node* copyRandomList(struct Node* head) {
    struct Node* cur1 = head, * cur2, * tmp, * guard, * tail;
    guard = tail = (struct Node*)malloc(sizeof(struct Node));
    guard->next = tail->next = NULL;
    while (cur1)
    {
        struct Node* new = (struct Node*)malloc(sizeof(struct Node));
        tail->next = new;
        tail = tail->next;
        tail->val = cur1->val;
        cur1 = cur1->next;
    }
    tail->next = NULL;
    cur1 = head;
    cur2 = guard->next;
    while (cur2)
    {
        int Num = Find_Num(head, cur1->random);
        struct Node* pos = guard->next;
        while (Num--)
        {
            pos = pos->next;
        }
        cur2->random = pos;
        cur2 = cur2->next;
        cur1 = cur1->next;
    }
    tmp = guard->next;
    free(guard);
    return tmp;
}